package com.yulan.backTrack;

import org.junit.Test;

/**
 * 1219. 黄金矿工
 */
public class LeetCode_1219 {


    int n,m;

    public int getMaximumGold(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        int res = 0;
        for(int i = 0; i<n; i++){
            for(int j = 0; j<m ;j++){
                if(grid[i][j] > 0)
                    res = Math.max(res,dfs(grid,i,j,0));
            }
        }

        return res;
    }


    public int dfs(int[][] matrix, int i, int j, int curProfit){
        if(i<0 || i>=n || j<0 || j>=m || matrix[i][j] == 0){
            return curProfit;
        }

        int cur = matrix[i][j];
        matrix[i][j] = 0;
        int a = dfs(matrix,i+1,j,curProfit+cur);
        int b = dfs(matrix,i-1,j,curProfit+cur);
        int c = dfs(matrix,i,j+1,curProfit+cur);
        int d = dfs(matrix,i,j-1,curProfit+cur);
        //回溯
        matrix[i][j] = cur;
        return Math.max(Math.max(a,b),Math.max(c,d));
    }

    @Test
    public void test(){
        int[][] grid ={
                {0,6,0},
                {5,8,7},
                {0,9,0}
        };
        System.out.println(getMaximumGold(grid));
    }


}
